/*
 * $Id: BaseString.h,v 1.8 2006-04-24 09:01:18 bacon Exp $
 */

#ifndef _XPP_BAS_BASESTRING_CLASS_
#define _XPP_BAS_BASESTRING_CLASS_

#include <xp/types.h>
#include <xp/macros.h>
#include <xp/bas/memory.h>
#include <xp/bas/stdarg.h>
#include <xp/bas/ctype.h>
#include <xp/bas/stdio.h>
#include <xpp/Hashable.h>
#include <xpp/RefCounted.h>

namespace xpp
{
	namespace bas
	{

		template <typename char_type> class BaseString;

		template <typename char_type>
		class BaseStringData: public RefCounted
		{
		protected:
			friend class BaseString<char_type>;

			BaseStringData (xp_size_t capacity,
				const char_type* str, xp_size_t offset, xp_size_t size)
			{
				xp_assert (capacity >= size);
				this->buffer = new char_type[capacity + 1];
				xp_memcpy (this->buffer,
					str + offset, size * xp_sizeof(char_type));
				this->buffer[size] = (char_type)0;
				this->size = size;
				this->capacity = capacity;
			}

		public:
			~BaseStringData () 
			{
				xp_assert (this->buffer != XP_NULL);
				delete[] this->buffer;
			}
		
		protected:	
			BaseStringData<char_type>* copy ()
			{
				return new BaseStringData<char_type> (
					this->capacity, this->buffer, 0, this->size);
			}
			BaseStringData<char_type>* copy (xp_size_t capacity)
			{
				return new BaseStringData<char_type> (
					capacity, this->buffer, 0, this->size);
			}

			xp_size_t capacity;	
			xp_size_t size;
			char_type* buffer;	
		};
	
		template <typename char_type>
		class BaseString: public Hashable
		{
		public:
			enum {
				DFL_CAPACITY = 128,
				INVALID_INDEX = ~(xp_size_t)0
			};

			BaseString ()
			{
				data = new BaseStringData<char_type> (
					round_capacity(DFL_CAPACITY), XP_NULL, 0, 0);
				data->ref ();
			}
			BaseString (xp_size_t capacity)
			{
				data = new BaseStringData<char_type> (
					round_capacity(capacity), XP_NULL, 0, 0);
				data->ref ();
			}
			BaseString (const char_type* str)
			{
				xp_size_t len = lengthOf (str);
				data = new BaseStringData<char_type> (
					round_capacity(len), str, 0, len);
				data->ref ();
			}
			BaseString (const char_type* str, xp_size_t offset, xp_size_t size)
			{
				data = new BaseStringData<char_type> (
					round_capacity(size), str, offset, size);
				data->ref ();
			}
			BaseString (const BaseString<char_type>& str)
			{
				data = str.data;
				data->ref ();
			}

			~BaseString () 
			{
				data->deref ();
			}

			xp_size_t size () const 
			{
				return data->size;
			}
			xp_size_t length () const 
			{
				return data->size;
			}
			xp_size_t capacity () const 
			{
				return data->capacity;
			}

			operator const char_type* () const 
			{
				return data->buffer;
			}

			const char_type* buffer() const
			{
				return data->buffer;
			}

			xp_size_t hashCode () const
			{
				return Hashable::hashCode (
					data->buffer, data->size * xp_sizeof(char_type));
			}

			const char_type& operator[] (xp_size_t index) const;

			BaseString<char_type>& operator= (const BaseString<char_type>& str);
			BaseString<char_type>& operator= (const char_type* str);
			BaseString<char_type>& operator= (const char_type c);

			BaseString<char_type>& operator+= (const BaseString<char_type>& str);
			BaseString<char_type>& operator+= (const char_type* str);
			BaseString<char_type>& operator+= (const char_type c);

			bool operator== (const BaseString<char_type>& str) const;
			bool operator!= (const BaseString<char_type>& str) const;

			bool operator== (const char_type* str) const;
			bool operator!= (const char_type* str) const;

			//
			// TODO: comparison, hash, trim, case-converting, etc
			// utf-8 encoding/decoding
			//

			char_type& charAt (xp_size_t index) 
			{
				xp_assert (index < data->size);
				return data->buffer[index];
			}
			const char_type& charAt (xp_size_t index) const 
			{
				xp_assert (index < data->size);
				return data->buffer[index];
			}
			void setCharAt (xp_size_t index, char_type c);
			
			void insert (xp_size_t index,
				const char_type* str, xp_size_t offset, xp_size_t size);
			void insert (xp_size_t index, const char_type* str);
			void insert (xp_size_t index, const char_type c);
			void insert (xp_size_t index, 
				const BaseString<char_type>& str, xp_size_t offset, xp_size_t size);
			void insert (xp_size_t index, const BaseString<char_type>& str);

			void prepend (const char_type* str, xp_size_t offset, xp_size_t size);
			void prepend (const char_type* str);
			void prepend (const char_type c);
			void prepend (const BaseString<char_type>& str, xp_size_t offset, xp_size_t size);
			void prepend (const BaseString<char_type>& str);

			void append (const char_type* str, xp_size_t offset, xp_size_t size);
			void append (const char_type* str);
			void append (const char_type c);
			void append (const BaseString<char_type>& str, xp_size_t offset, xp_size_t size);
			void append (const BaseString<char_type>& str);

			void set (const char_type* str, xp_size_t offset, xp_size_t size);
			void set (const char_type* str);
			void set (const char_type c);
			void set (const BaseString<char_type>& str, xp_size_t offset, xp_size_t size);
			void set (const BaseString<char_type>& str);

			void remove (xp_size_t offset, xp_size_t size);
			void remove ();

			void invert (xp_size_t offset, xp_size_t size);
			void invert ();

			void replace (xp_size_t offset, xp_size_t size,
				const char_type* str, xp_size_t soffset, xp_size_t ssize);
			void replace (xp_size_t offset, xp_size_t size, const char_type* str);
			void replace (xp_size_t offset, xp_size_t size,
				const BaseString<char_type>& str, xp_size_t soffset, xp_size_t ssize);
			void replace (xp_size_t offset, xp_size_t size, 
				const BaseString<char_type>& str);

			void replaceAll (xp_size_t index,
				const char_type* str1, const char_type* str2);
			void replaceAll (const char_type* str1, const char_type* str2);
			void replaceAll (xp_size_t index, 
				const BaseString<char_type>& str1,
				const BaseString<char_type>& str2);
			void replaceAll (
				const BaseString<char_type>& str1,
				const BaseString<char_type>& str2);
		
			BaseString<char_type> substring (xp_size_t offset);
			BaseString<char_type> substring (xp_size_t offset, xp_size_t size);

			xp_size_t indexOf (xp_size_t index,
				const char_type* str, xp_size_t offset, xp_size_t size);
			xp_size_t indexOf (xp_size_t index, const char_type* str);
			xp_size_t indexOf (const char_type* str, xp_size_t offset, xp_size_t size);
			xp_size_t indexOf (const char_type* str);
			xp_size_t indexOf (xp_size_t index,
				const BaseString<char_type>& str, xp_size_t offset, xp_size_t size);
			xp_size_t indexOf (xp_size_t index, const BaseString<char_type>& str);
			xp_size_t indexOf (
				const BaseString<char_type>& str, xp_size_t offset, xp_size_t size);
			xp_size_t indexOf (const BaseString<char_type>& str);
			xp_size_t indexOf (xp_size_t index, char_type c);
			xp_size_t indexOf (char_type c);

			xp_size_t lastIndexOf (xp_size_t index,
				const char_type* str, xp_size_t offset, xp_size_t size);
			xp_size_t lastIndexOf (xp_size_t index, const char_type* str);
			xp_size_t lastIndexOf (
				const char_type* str, xp_size_t offset, xp_size_t size);
			xp_size_t lastIndexOf (const char_type* str);
			xp_size_t lastIndexOf (xp_size_t index,
				const BaseString<char_type>& str, xp_size_t offset, xp_size_t size);
			xp_size_t lastIndexOf (xp_size_t index, const BaseString<char_type>& str);
			xp_size_t lastIndexOf (
				const BaseString<char_type>& str, xp_size_t offset, xp_size_t size);
			xp_size_t lastIndexOf (const BaseString<char_type>& str);
			xp_size_t lastIndexOf (xp_size_t index, char_type c);
			xp_size_t lastIndexOf (char_type c);

			bool beginsWith (const char_type* str) const
			{
				xp_size_t idx = 0;
				while (*str != (char_type)0) {
					if (idx >= data->size) return false;
					if (data->buffer[idx] != *str) return false;
					idx++; str++;
				}
				return true;
			}

			bool beginsWith (const char_type* str, const xp_size_t len) const
			{
				const char_type* end = str + len;
				xp_size_t idx = 0;

				while (str < end) {
					if (idx >= data->size) return false;
					if (data->buffer[idx] != *str) return false;
					idx++; str++;
				}
				return true;
			}

			xp_size_t touppercase ()
			{
				if (data->isShared()) {
					BaseStringData<char_type>* t = data->copy ();
					data->deref (); data = t; data->ref ();
				}

				return touppercase (data->buffer);
			}

			xp_size_t tolowercase ()
			{
				if (data->isShared()) {
					BaseStringData<char_type>* t = data->copy ();
					data->deref (); data = t; data->ref ();
				}
				return tolowercase (data->buffer);
			}

			xp_size_t trim ()
			{
				if (data->isShared()) {
					BaseStringData<char_type>* t = data->copy ();
					data->deref (); data = t; data->ref ();
				}

				data->size = trim (data->buffer);
				return data->size;
			}

			static xp_size_t lengthOf (const char_type* str);

			static char_type* find (const char_type* str, char_type c);

			static int compare (
				const char_type* s1, const char_type* s2);
			static int compare (
				const char_type* s1, const char_type* s2, xp_size_t count);
			static int compare (
				const char_type* s1, xp_size_t s1_count, const char_type* s2);

			static xp_size_t copy (
				char_type* dst, xp_size_t dsz, const char_type* src, xp_size_t ssz);
			static xp_size_t copy (
				char_type* dst, xp_size_t dsz, const char_type* src);
			static xp_size_t copy (char_type* dst, const char_type* src);

			static xp_size_t tolowercase (char_type* str);
			static xp_size_t touppercase (char_type* str);
			//static char_type* tolowercase (char_type* str, xp_size_t sz);
			//static char_type* touppercase (char_type* str, xp_size_t sz);
			static xp_size_t trim (char_type* str);

			static xp_size_t format (
				char_type* buf, xp_size_t size, const char_type* fmt, ...);
			static xp_size_t formatv (
				char_type* buf, xp_size_t size, const char_type* fmt, xp_va_list ap);

			static char_type* tokenize (
				const char_type* s, const char_type* delim, 
				char_type** tok, xp_size_t* tok_len);

			static bool aredigits (const char_type* s)
			{
				while (*s != (char_type)0) {
					if (!xp_isdigit(*s)) return false;
					s++;
				}
				return true;
			}

			static bool aredigits (const char_type* s, xp_size_t len)
			{
				const char_type* end = s + len;
				while (s < end) {
					if (!xp_isdigit(*s)) return false;
					s++;
				}
				return true;
			}

			static bool aresigneddigits (const char_type* s)
			{
				if (*s == (char_type)'+' || *s == (char_type)'-') {
					s++;
					if (*s == (char_type)0) return false;
				}

				while (*s != (char_type)0) {
					if (!xp_isdigit(*s)) return false;
					s++;
				}
				return true;
			}

			static bool aresigneddigits (const char_type* s, xp_size_t len)
			{
				const char_type* end = s + len;
				if (*s == (char_type)'+' || *s == (char_type)'-') {
					s++;
					if (s >= end) return false;
				}

				while (s < end) {
					if (!xp_isdigit(*s)) return false;
					s++;
				}
				return true;
			}

		protected:
			mutable BaseStringData<char_type>* data;	

		private:
			static xp_size_t round_capacity (xp_size_t n) 
			{
				if (n == 0) n = 1;
				return 
					(n + (xp_size_t)DFL_CAPACITY - 1) & 
					~((xp_size_t)DFL_CAPACITY - (xp_size_t)1);
			}
		};

		template <typename char_type>
		const char_type& BaseString<char_type>::operator[] (xp_size_t index) const
		{
			xp_assert (index < data->size);

			if (data->isShared()) {
				BaseStringData<char_type>* t = data->copy ();
				data->deref (); data = t; data->ref ();
			}
			return data->buffer[index];
		}

		template <typename char_type>
		BaseString<char_type>& BaseString<char_type>::operator= (
			const BaseString<char_type>& str) 
		{
			if (data == str.data) return *this;
			data->deref ();
			data = str.data;	
			data->ref ();
			return *this;
		}

		template <typename char_type>
		BaseString<char_type>& BaseString<char_type>::operator= (
			const char_type* str)
		{
			if (data->buffer == str) return *this;
			remove ();
			insert (0, str);
			return *this;
		}

		template <typename char_type>
		BaseString<char_type>& BaseString<char_type>::operator= (
			const char_type c)
		{
			remove ();
			insert (0, &c, 0, 1);
			return *this;
		}

		template <typename char_type>
		BaseString<char_type>& BaseString<char_type>::operator+= (
			const BaseString<char_type>& str)
		{
			insert (data->size, str.data->buffer, 0, str.data->size);
			return *this;
		}

		template <typename char_type>
		BaseString<char_type>& BaseString<char_type>::operator+= (
			const char_type* str)
		{
			insert (data->size, str);
			return *this;
		}

		template <typename char_type>
		BaseString<char_type>& BaseString<char_type>::operator+= (
			const char_type c)
		{
			insert (data->size, &c, 0, 1);
			return *this;
		}

		template <typename char_type>
		bool BaseString<char_type>::operator== (
			const BaseString<char_type>& str) const
		{
			if (data->size != str.data->size) return false;
			return xp_memcmp (
				data->buffer, str.data->buffer,
				xp_sizeof(char_type) * data->size) == 0;
		}

		template <typename char_type>
		bool BaseString<char_type>::operator!= (
			const BaseString<char_type>& str) const
		{
			return !operator==(str);
		}

		template <typename char_type>
		bool BaseString<char_type>::operator== (const char_type* str) const
		{
			return compare (data->buffer, str) == 0;
		}
		
		template <typename char_type>
		bool BaseString<char_type>::operator!= (const char_type* str) const
		{
			return compare (data->buffer, str) != 0;
		}
		
		template <typename char_type>
		void BaseString<char_type>::setCharAt (xp_size_t index, char_type c)
		{
			xp_assert (index < data->size);

			if (data->isShared()) {
				BaseStringData<char_type>* t = data->copy ();
				data->deref (); data = t; data->ref ();
			}
			data->buffer[index] = c;
		}

		template <typename char_type>
		void BaseString<char_type>::insert (xp_size_t index, 
			const char_type* str, xp_size_t offset, xp_size_t size)
		{
			if (index >= data->size) index = data->size;

			//
			// When the same instance is inserted as in n.insert(index, n) which
			// finally calls n.insert(index. n.data->buffer, 0, n.data->size),
			// if n is not shared and should be copied, calling deref to it 
			// immediately after it's copied will destroy n.data refered to by
			// str/offset/size. So the deref must be called after copying is
			// done.
			//

			BaseStringData<char_type>* old_data = XP_NULL;
			xp_size_t new_size = data->size + size;

			if (data->isShared()) {
				BaseStringData<char_type>* t;
				if (new_size > data->capacity) 
					t = data->copy (round_capacity(new_size));
				else t = data->copy ();
				//data->deref (); data = t; data->ref ();
				old_data = data; data = t; data->ref ();
			}
			else if (new_size > data->capacity) {
				BaseStringData<char_type>* t = data->copy (round_capacity(new_size));
				//data->deref (); data = t; data->ref ();
				old_data = data; data = t; data->ref ();
			}
			
			char_type* p = data->buffer + index;
			xp_memmove (
				p + size, p,
				(data->size - index) * xp_sizeof(char_type));
			xp_memcpy (
				p, str + offset, size * xp_sizeof(char_type));

			data->size = new_size;
			data->buffer[new_size] = (char_type)0;

			if (old_data) old_data->deref ();
		}

		template <typename char_type>
		void BaseString<char_type>::insert (xp_size_t index, const char_type* str)
		{
			insert (index, str, 0, lengthOf(str));
		}

		template <typename char_type>
		void BaseString<char_type>::insert (xp_size_t index, const char_type c)
		{
			insert (index, &c, 0, 1);
		}

		template <typename char_type>
		void BaseString<char_type>::insert (xp_size_t index, 
			const BaseString<char_type>& str, xp_size_t offset, xp_size_t size)
		{
			xp_assert (offset + size <= str.data->size);
			insert (index, str.data->buffer, offset, size);
		}

		template <typename char_type>
		void BaseString<char_type>::insert (
			xp_size_t index, const BaseString<char_type>& str)
		{
			insert (index, str.data->buffer, 0, str.data->size);
		}

		template <typename char_type>
		void BaseString<char_type>::prepend (
			const char_type* str, xp_size_t offset, xp_size_t size)
		{
			insert (0, str, offset, size);	
		}

		template <typename char_type>
		void BaseString<char_type>::prepend (const char_type* str)
		{
			insert (0, str);
		}

		template <typename char_type>
		void BaseString<char_type>::prepend (const char_type c)
		{
			insert (0, c);
		}

		template <typename char_type>
		void BaseString<char_type>::prepend (
			const BaseString<char_type>& str, xp_size_t offset, xp_size_t size)
		{
			insert (0, str, offset, size);
		}

		template <typename char_type>
		void BaseString<char_type>::prepend (const BaseString<char_type>& str)
		{
			insert (0, str);
		}

		template <typename char_type>
		void BaseString<char_type>::append (
			const char_type* str, xp_size_t offset, xp_size_t size)
		{
			insert (data->size, str, offset, size);	
		}

		template <typename char_type>
		void BaseString<char_type>::append (const char_type* str)
		{
			insert (data->size, str);
		}

		template <typename char_type>
		void BaseString<char_type>::append (const char_type c)
		{
			insert (data->size, c);
		}

		template <typename char_type>
		void BaseString<char_type>::append (
			const BaseString<char_type>& str, xp_size_t offset, xp_size_t size)
		{
			insert (data->size, str, offset, size);
		}

		template <typename char_type>
		void BaseString<char_type>::append (const BaseString<char_type>& str)
		{
			insert (data->size, str);
		}

		template <typename char_type>
		void BaseString<char_type>::set (
			const char_type* str, xp_size_t offset, xp_size_t size)
		{
			remove ();
			insert (0, str, offset, size);	
		}

		template <typename char_type>
		void BaseString<char_type>::set (const char_type* str)
		{
			remove ();
			insert (0, str);
		}

		template <typename char_type>
		void BaseString<char_type>::set (const char_type c)
		{
			remove ();
			insert (0, c);
		}

		template <typename char_type>
		void BaseString<char_type>::set (
			const BaseString<char_type>& str, xp_size_t offset, xp_size_t size)
		{
			remove ();
			insert (0, str, offset, size);
		}

		template <typename char_type>
		void BaseString<char_type>::set (const BaseString<char_type>& str)
		{
			operator= (str);
		}

		template <typename char_type>
		void BaseString<char_type>::remove (xp_size_t offset, xp_size_t size)
		{
			xp_assert (offset + size <= data->size);

			if (data->isShared()) {
				BaseStringData<char_type>* t = data->copy ();
				data->deref (); data = t; data->ref ();
			}

			char_type* p = data->buffer + offset;
			xp_memcpy (p, p + size, 
				(data->size - offset - size + 1) * xp_sizeof(char_type));
			data->size -= size;	
		}

		template <typename char_type>
		void BaseString<char_type>::remove ()
		{
			remove (0, data->size);
		}

		template <typename char_type>
		void BaseString<char_type>::invert (xp_size_t offset, xp_size_t size)
		{
			xp_assert (offset + size <= data->size);

			if (data->isShared()) {
				BaseStringData<char_type>* t = data->copy ();
				data->deref (); data = t; data->ref ();
			}

			char_type c;
			xp_size_t i = offset + size;
			for (xp_size_t j = offset; j < --i; j++) {
				c = data->buffer[j];	
				data->buffer[j] = data->buffer[i];
				data->buffer[i] = c;
			}
		}

		template <typename char_type>
		void BaseString<char_type>::invert ()
		{
			invert (0, data->size);
		}

		template <typename char_type>
		void BaseString<char_type>::replace (xp_size_t offset, xp_size_t size, 
			const char_type* str, xp_size_t soffset, xp_size_t ssize)
		{
			remove (offset, size);	
			insert (offset, str, soffset, ssize);
		}

		template <typename char_type>
		void BaseString<char_type>::replace (
			xp_size_t offset, xp_size_t size, const char_type* str)
		{
			remove (offset, size);
			insert (offset, str, 0, lengthOf(str));
		}

		template <typename char_type>
		void BaseString<char_type>::replace (xp_size_t offset, xp_size_t size,
			const BaseString<char_type>& str, xp_size_t soffset, xp_size_t ssize)
		{
			remove (offset, size);	
			insert (offset, str, soffset, ssize);
		}

		template <typename char_type>
		void BaseString<char_type>::replace (
			xp_size_t offset, xp_size_t size, const BaseString<char_type>& str)
		{
			remove (offset, size);
			insert (offset, str);
		}

		template <typename char_type>
		void BaseString<char_type>::replaceAll (xp_size_t index,
			const char_type* str1, const char_type* str2)
		{
			xp_size_t len1 = lengthOf(str1);
			xp_size_t len2 = lengthOf(str2);
			while ((index = indexOf(index, str1, 0, len1)) != INVALID_INDEX) {
				replace (index, len1, str2, 0, len2);
				index += len2;
			}
		}

		template <typename char_type>
		void BaseString<char_type>::replaceAll (
			const char_type* str1, const char_type* str2)
		{
			replaceAll (0, str1, str2);
		}

		template <typename char_type>
		void BaseString<char_type>::replaceAll (
			xp_size_t index,
			const BaseString<char_type>& str1,
			const BaseString<char_type>& str2)
		{
			while ((index = indexOf(index, str1)) != INVALID_INDEX) {
				replace (index, str1.data->size, str2);
				index += str2.data->size;
			}
		}

		template <typename char_type>
		void BaseString<char_type>::replaceAll (
			const BaseString<char_type>& str1,
			const BaseString<char_type>& str2)
		{
			replaceAll (0, str1, str2);
		}

		template <typename char_type>
		BaseString<char_type> BaseString<char_type>::substring (xp_size_t offset)
		{
			xp_assert (offset < data->size);
			return BaseString<char_type> (
				data->buffer, offset, data->size - offset);
		}

		template <typename char_type>
		BaseString<char_type> BaseString<char_type>::substring (
			xp_size_t offset, xp_size_t size)
		{
			xp_assert (offset + size <= data->size);
			return BaseString<char_type> (
				data->buffer, offset, size);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::indexOf (
			xp_size_t index, const char_type* str, xp_size_t offset, xp_size_t size)
		{
			if (size == 0) return index;
			if (size > data->size) return INVALID_INDEX;
			if (index >= data->size) return INVALID_INDEX;

			/*
			char_type first = str[offset];
			xp_size_t i = index;
			xp_size_t max = data->size - size;
			char_type* p = data->buffer;

		loop_indexOf:
			while (i <= max && p[i] != first) i++;
			if (i > max) return INVALID_INDEX;

			xp_size_t j = i + 1;
			xp_size_t end = j + size - 1;
			xp_size_t k = offset + 1;
			while (j < end) {
				if (p[j++] != str[k++]) {
					i++;
					goto loop_indexOf;
				}
			}
			return i;
			*/

			char_type first = str[offset];
			char_type* s1 = data->buffer + index;
			char_type* e1 = data->buffer + data->size - size;
			char_type* p1 = s1;

		loop_indexOf:
			while (p1 <= e1 && *p1 != first) p1++;
			if (p1 > e1) return INVALID_INDEX;

			const char_type* s2 = str + offset + 1;

			char_type* p2 = p1 + 1;
			char_type* e2 = p2 + size - 1;

			while (p2 < e2) {
				if (*p2++ != *s2++) {
					p1++;
					goto loop_indexOf;
				}
			}

			return p1 - data->buffer;
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::indexOf (
			xp_size_t index, const char_type* str)
		{
			return indexOf (index, str, 0, lengthOf(str));
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::indexOf (
			const char_type* str, xp_size_t offset, xp_size_t size)
		{
			return indexOf (0, str, offset, size);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::indexOf (const char_type* str)
		{
			return indexOf (0, str);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::indexOf (xp_size_t index,
			const BaseString<char_type>& str, xp_size_t offset, xp_size_t size)
		{
			xp_assert (offset + size <= str.data->size);
			return indexOf (index, str.data->buffer, offset, size);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::indexOf (
			xp_size_t index, const BaseString<char_type>& str)
		{
			return indexOf (index, str.data->buffer, 0, str.data->size);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::indexOf (
			const BaseString<char_type>& str, xp_size_t offset, xp_size_t size)
		{
			xp_assert (offset + size <= str.data->size);
			return indexOf (0, str.data->buffer, offset, size);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::indexOf (const BaseString<char_type>& str)
		{
			return indexOf (0, str.data->buffer, 0, str.data->size);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::indexOf (xp_size_t index, char_type c)
		{
			if (index >= data->size) return INVALID_INDEX;

			char_type* s = data->buffer + index;
			char_type* e = data->buffer + data->size;

			for (char_type* p = s; p < e; p++) {
				if (*p == c) return p - s;
			}

			return INVALID_INDEX;
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::indexOf (char_type c)
		{
			return indexOf (0, c);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::lastIndexOf (
			xp_size_t index, const char_type* str, xp_size_t offset, xp_size_t size)
		{
			if (size == 0) return index;
			if (size > data->size) return INVALID_INDEX;
			if (index >= data->size) index = data->size - 1;

			xp_size_t strLast = offset + size - 1;
			char_type last = str[strLast];
			xp_size_t min = size - 1;
			xp_size_t i = min + index;
			char_type* p = data->buffer;

		loop_lastIndexOf:
			while (i >= min && p[i] != last) i--;
			if (i < min) return INVALID_INDEX;

			xp_size_t j = i - 1;
			xp_size_t start = j - size + 1;
			xp_size_t k = strLast - 1;
			while (j > start) {
				if (p[j--] != str[k--]) {
					i--;
					goto loop_lastIndexOf;
				}
			}
			return start + 1;
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::lastIndexOf (
			xp_size_t index, const char_type* str)
		{
			return lastIndexOf (index, str, 0, lengthOf(str));
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::lastIndexOf (
			const char_type* str, xp_size_t offset, xp_size_t size)
		{
			return lastIndexOf (data->size - 1, str, offset, size);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::lastIndexOf (const char_type* str)
		{
			return lastIndexOf (data->size - 1, str);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::lastIndexOf (xp_size_t index,
			const BaseString<char_type>& str, xp_size_t offset, xp_size_t size)
		{
			xp_assert (offset + size <= str.data->size);
			return lastIndexOf (index, str.data->buffer, offset, size);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::lastIndexOf (
			xp_size_t index, const BaseString<char_type>& str)
		{
			return lastIndexOf (index, str.data->buffer, 0, str.data->size);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::lastIndexOf (
			const BaseString<char_type>& str, xp_size_t offset, xp_size_t size)
		{
			xp_assert (offset + size <= str.data->size);
			return lastIndexOf (
				data->size - 1, str.data->buffer, offset, size);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::lastIndexOf (
			const BaseString<char_type>& str)
		{
			return lastIndexOf (
				data->size - 1, str.data->buffer, 0, str.data->size);
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::lastIndexOf (xp_size_t index, char_type c)
		{
			if (index >= data->size) index = data->size - 1;

			char_type* s = data->buffer;
			char_type* e = data->buffer + index;

			for (char_type* p = e; p >= s; p--) {
				if (*p == c) return p - s;
			}

			return INVALID_INDEX;
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::lastIndexOf (char_type c)
		{
			return lastIndexOf (data->size - 1, c);
		}


		template <typename char_type>
		xp_size_t BaseString<char_type>::lengthOf (const char_type* str)
		{
			//return ::wcslen (str);
			xp_size_t len = 0;
			while (*str++ != (char_type)0) len++;
			return len;
		}

		template <typename char_type>
		char_type* BaseString<char_type>::find (
			const char_type* str, char_type c)
		{
			while (*str != (char_type)0) {
				if (*str == c) return (char_type*)str;
				str++;
			}
			return XP_NULL;
		}

		template <typename char_type>
		int BaseString<char_type>::compare (
			const char_type* s1, const char_type* s2)
		{
			//return ::wcscmp (s1, s2);
			while (*s1 == *s2 && *s2 != (char_type)0) s1++, s2++;
			if (*s1 > *s2) return 1;
			else if (*s1 < *s2) return -1;
			return 0;
		}

		template <typename char_type>
		int BaseString<char_type>::compare (
			const char_type* s1, const char_type* s2, xp_size_t count)
		{
			//return ::wcsncmp (s1, s2);
			if (count == 0) return 0;

			while (--count && *s1 != (char_type)0 && *s1 == *s2) s1++, s2++;
			if (*s1 > *s2) return 1;
			else if (*s1 < *s2) return -1;
			return 0;
		}

		template <typename char_type>
		int BaseString<char_type>::compare (
			const char_type* s1, xp_size_t s1_count, const char_type* s2)
		{
			xp_size_t idx = 0;
			while (idx < s1_count && 
				s2[idx] != (char_type)0 && s1[idx] == s2[idx]) idx++;
			if (idx == s1_count && s2[idx] == (char_type)0) return 0;
			if (s1[idx] == s2[idx]) return (s1_count > idx)? 1: -1;
			return (s1[idx] > s2[idx])? 1: -1;
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::copy (
			char_type* dst, xp_size_t dsz, const char_type* src, xp_size_t ssz)
		{
			xp_assert (dsz > 0);
			xp_size_t sz = (dsz - 1 >= ssz)? ssz: dsz - 1;	
			xp_memcpy (dst, src, sz * xp_sizeof(char_type));
			dst[sz] = (char_type)0;
			return sz;
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::copy (
			char_type* dst, xp_size_t dsz, const char_type* src)
		{
			return copy (dst, dsz, src, lengthOf(src));
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::copy (
			char_type* dst, const char_type* src)
		{
			const char_type* p = src;
			while (*p != (char_type)0) *dst++ = *p++;
			*dst = (char_type)0;	
			return p - src;
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::tolowercase (char_type* str)
		{
			char_type* p = str;
			while (*p != (char_type)0) {
				*p = xp_tolower(*p);
				p++;
			}
			return p - str;
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::touppercase (char_type* str)
		{
			char_type* p = str;
			while (*p != (char_type)0) {
				*p = xp_toupper(*p);
				p++;
			}
			return p - str;
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::trim (char_type* str)
		{
			char_type* p = str, * s = XP_NULL, * e = XP_NULL;

			while (*p != (char_type)0) {
				if (!xp_isspace(*p)) {
					if (s == XP_NULL) s = p;
					e = p;
				}
				p++;
			}

			if (e != XP_NULL) {
				e[1] = (char_type)0;
				xp_memcpy (str, s, (e - s + 2) * xp_sizeof(char_type));
				return e - s + 1;
			}

			str[0] = (char_type)0;
			return 0;
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::format (
			char_type* buf, xp_size_t size, const char_type* fmt, ...)
		{
			xp_assert (size > 0);
		
			xp_va_list ap;
			xp_va_start (ap, fmt);
		
			int n = ::xp_vsprintf (buf, size, fmt, ap);
			xp_va_end (ap);
		
			if (n == -1 || (xp_size_t)n >= size) {
				buf[size - 1] = (char_type)0;
				return size - 1;
			}
			return (xp_size_t)n;
		}

		template <typename char_type>
		xp_size_t BaseString<char_type>::formatv (
			char_type* buf, xp_size_t size, const char_type* fmt, xp_va_list ap)
		{
			xp_assert (size > 0);
		
			int n = ::xp_vsprintf (buf, size, fmt, ap);
			if (n == -1 || (xp_size_t)n >= size) {
				buf[size - 1] = (char_type)0;
				return size - 1;
			}
			return (xp_size_t)n;
		}

		template <class char_type>
		char_type* BaseString<char_type>::tokenize (
			const char_type* s, const char_type* delim, 
			char_type** tok, xp_size_t* tok_len)
		{
			const char_type* p = s, *d;
			const char_type* sp = XP_NULL, * ep = XP_NULL;
			char_type c; 
			int delim_mode;
		
			// skip preceding space char_typeacters
			while (/* *p && */ xp_isspace(*p)) p++;
		
			if (delim == XP_NULL) delim_mode = 0;
			else {
				delim_mode = 1;
				for (d = delim; *d; d++) 
					if (!xp_isspace(*d)) delim_mode = 2;
			}
		
			if (delim_mode == 0) { 
				// when XP_NULL is given as "delim", it has an effect of cutting
				// preceding and trailing space char_typeacters off "s".
				while ((c = *p)) {
					if (!xp_isspace(c)) {
						if (sp == XP_NULL) sp = p;
						ep = p;
					}
					p++;
				}
			}
			else if (delim_mode == 1) {
				while ((c = *p)) {
					if (xp_isspace(c)) break;
		
					if (sp == XP_NULL) sp = p;
					ep = p++;
				}
			}
			else { /* if (delim_mode == 2) { */
				while ((c = *p)) {
					if (xp_isspace(c)) {
						p++;
						continue;
					}
					for (d = delim; *d; d++) {
						if (c == *d) {
							goto exit_loop;
						}
					}
					if (sp == XP_NULL) sp = p;
					ep = p++;
				}
			}
		
		exit_loop:
			if (sp == XP_NULL) {
				*tok = XP_NULL;
				*tok_len = (xp_size_t)0;
			}
			else {
				*tok = (char_type*)sp;
				*tok_len = (xp_size_t)(ep - sp + 1);
			}
			if (c == (char_type)0) return XP_NULL;
			return (char_type*)++p;
		}
		
	}
}

#endif
